/*
 * https://leetcode-cn.com/problems/accounts-merge/
 * 并查集
 */
typedef struct {
    char *email;
    int  idx;
    UT_hash_handle hh;
} ut_hash_t;
ut_hash_t *email_table = NULL;
int find(int *parent, int x) { /* 并查集find */
    while (parent[x] != x) x = parent[x];
    return x;
}
void merge(int *parent, int x, int y) { /* 并查集合并 */
    int root1 = find(parent, x);
    int root2 = find(parent, y);
    if (root1 == root2) return;
    parent[root1] = root2;
}
int cmp(ut_hash_t *a, ut_hash_t *b) {
    return strcmp(a->email, b->email);
}
char *** accountsMerge(char *** accounts, int accountsSize, int* accountsColSize, int* returnSize, int** returnColumnSizes){
    email_table    = NULL;
    int  *map     = (int*)malloc(sizeof(int) * accountsSize);
    int  *parent  = (int*)malloc(sizeof(int) * accountsSize);
    char ***res   = (char***)malloc(sizeof(char**) * accountsSize);
    int  *ret_col  = (int*)malloc(sizeof(int) * accountsSize);
    int  cnt  = 0;
    char *email   = NULL;
    ut_hash_t *s   = NULL;
    ut_hash_t *tmp = NULL;
    memset(ret_col, 0, sizeof(int) * accountsSize);
    for (int i = 0; i < accountsSize; i++) {/* parent和map初始化 */
        parent[i] = i;
        map[i]    = -1;
        res[i]    = (char**)malloc(sizeof(char*) * 10000);
    }
    for (int i = 0; i < accountsSize; i++) { /* 将email存入hash中, idx为val值 */
        for (int j = 1; j < accountsColSize[i]; j++) {
            email = accounts[i][j];
            HASH_FIND_STR(email_table, email, s);
            if (s == NULL) {
                s = malloc(sizeof(ut_hash_t));
                s->email = email;
                s->idx   = i;
                HASH_ADD_STR(email_table, email, s);
            } else {
                merge(parent, i, s->idx);
            }
        }
    }
    HASH_SORT(email_table, cmp);
    HASH_ITER(hh, email_table, s, tmp) { /* 遍历hash表, 将对应email存入对应的res数组中 */
        int idx = find(parent, s->idx);
        if (map[idx] == -1) {   /* 并查集未出现过, 新的下标存储 */
            res[cnt][ret_col[cnt]++] = accounts[idx][0];
            res[cnt][ret_col[cnt]++] = s->email;
            map[idx] = cnt++;
        } else {               /* 属于某个并查集, 存储在老的下标下 */
            int pre_idx = map[idx];
            res[pre_idx][ret_col[pre_idx]++] = s->email;
        }
    }
    *returnSize        = cnt;
    *returnColumnSizes = ret_col;
    return res;
}